558A - Lala Land and Apple Trees - CodeForces Solution

#include <iostream>
#include <algorithm>

/*
https://codeforces.com/contest/558/problem/A

Amr lives in Lala Land. Lala Land is a very beautiful country that is located on a coordinate line.
Lala Land is famous with its apple trees growing everywhere.

Lala Land has exactly n apple trees. Tree number i is located in a position xi and has ai apples growing on it.
Amr wants to collect apples from the apple trees.

Amr currently stands in x = 0 position. At the beginning, he can choose whether to go right or left.
He'll continue in his direction until he meets an apple tree he didn't visit before.
He'll take all of its apples and then reverse his direction, continue walking in this direction until he meets another apple tree he didn't visit before and so on.

In the other words, Amr reverses his direction when visiting each new apple tree. 
Amr will stop collecting apples when there are no more trees he didn't visit in the direction he is facing.

What is the maximum number of apples he can collect?

Input
The first line contains one number n (1 ≤ n ≤ 100), the number of apple trees in Lala Land.
The following n lines contains two integers each xi, ai (-10^5 ≤ xi ≤ 10^5, xi ≠ 0, 1 ≤ ai ≤ 10^5), representing the position of the i-th tree and number of apples on it.
It's guaranteed that there is at most one apple tree at each coordinate. It's guaranteed that no tree grows in point 0.

Output
Output the maximum number of apples Amr can collect.
*/

using namespace std;

struct Tree {
    int xi, ai;

    Tree(int xi = 0, int ai = 0) {
        // Set the x coordinate and number of apples.
        this->xi = xi;
        this->ai = ai;
    }

    bool operator < (Tree t1) {
        if(this->xi > 0 && t1.xi > 0) {
            // In case two trees have positive x coordinates, then compare them in ascending order, based on x coordinate.
            return (this->xi < t1.xi);
        }
        
        // Otherwise, if trees have negative x coordinates, then compare them in descending order, based on x coordinate.
        return (this->xi > t1.xi);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Input the number of trees.
    int n_trees;
    cin >> n_trees;

    // Keep track of trees that are on positive/negative side of the axis.
    int pos_len = 0, neg_len = 0;
    Tree positive_trees[100]; 
    Tree negative_trees[100];
    int xi, ai;

    // Input the xi and ai for each tree.
    for(int i = 0; i < n_trees; ++i) {
        cin >> xi >> ai;

        if(xi > 0) {
            // In case the xi is greater than zero, store them in positive array.
            positive_trees[pos_len].xi = xi;
            positive_trees[pos_len++].ai = ai;
        }
        else {
            // Otherwise (doesn't include 0 as xi != 0 according to the text), store them in neagtive array.
            negative_trees[neg_len].xi = xi;
            negative_trees[neg_len++].ai = ai;
        }
    }

    // Sort trees with positive coordinate in ascending order.
    sort(positive_trees, positive_trees + pos_len);

    // Sort trees with negative coordinate in descending order.
    sort(negative_trees, negative_trees + neg_len);

    // Variables that are used to start with right first direction.
    long long apples_rf = 0; 
    int pos_rf = 0, neg_rf = 0;
    bool right_rf = true, over_rf = false; 

    // Variables that are used to start with left first direction.
    long long apples_lf = 0;
    int pos_lf = 0, neg_lf = 0;
    bool right_lf = false, over_lf = false;

    while(!over_rf || !over_lf) {
        if(!over_rf && right_rf && pos_rf < pos_len) {
            // If it isn't over, and if the right first direction is set to right, and if we have positive trees left to take apples from.
            // Take the apples from the closest tree, and switch direction.
            apples_rf += positive_trees[pos_rf++].ai;
            right_rf = !right_rf;
        }    
        else if(!over_rf && !right_rf && neg_rf < neg_len) {
            // If it isn't over, and if the right first direction is set to left, and if we have negative trees left to take apples from.
            // Take the apples from the closest tree, and switch direction.
            apples_rf += negative_trees[neg_rf++].ai;
            right_rf = !right_rf;
        } 
        else {
            // Otherwise, we are facing a direction where there are no trees to take apples from.
            // This means for the right first direction it is over.
            over_rf = true;
        }

        // Do it similarly for the left first direction.
        if(!over_lf && right_lf && pos_lf < pos_len) {
            apples_lf += positive_trees[pos_lf++].ai;
            right_lf = !right_lf;
        }    
        else if(!over_lf && !right_lf && neg_lf < neg_len) {
            apples_lf += negative_trees[neg_lf++].ai;
            right_lf = !right_lf;
        }
        else {
            over_lf = true;
        }
    }

    // Output the maximum number of apples that could have been collected out of the two directions.
    cout << max(apples_rf, apples_lf);    

    return 0;
}